package com.cat.dataStructure;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/find-substring-with-given-hash-value/?envType=problem-list-v2&envId=rFbd9B5V
 * @create 2025/9/27 15:50
 * @since JDK17
 */

public class Solution82 {
    public String subStrHash(String s, int power, int modulo, int k, int hashValue) {
        char[] arr = s.toCharArray();
        int n = arr.length;
        long h = 0, p = 1;
        for (int i = n - 1; i >= n - k; i--) {
            h = (h * power + (arr[i] - 'a' + 1)) % modulo;
            p = p * power % modulo;
        }
        int ans = h == hashValue ? n - k : 0;
        for (int i = n - k - 1; i >= 0; i--) {
            h = (h * power + (arr[i] - 'a' + 1) - p * (arr[i + k] - 'a' + 1) % modulo + modulo) % modulo;
            if (h == hashValue) {
                ans = i;
            }
        }

        return s.substring(ans, ans + k);
    }
}
